home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / REXPR.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  10KB  |  504 lines
  1. /*
  2.  * This file contains code for
  3.  *
  4.  *      int rexpr(char *expr, char *s);
  5.  *
  6.  * which answers
  7.  *
  8.  *      1 if 's' is in the language described by the regular expression 'expr'
  9.  *      0 if it is not
  10.  *     -1 if the regular expression is invalid
  11.  *
  12.  * Language membership is determined by constructing a non-deterministic
  13.  * finite automata (NFA) from the regular expression.  A depth-
  14.  * first-search is performed on the NFA (graph) to check for a match of 's'.
  15.  * Each non-epsilon arc consumes one character from 's'.  Backtracking is
  16.  * performed to check all possible paths through the NFA.
  17.  *
  18.  * Regular expressions follow the meta-language:
  19.  *
  20.  * <regExpr>        ::= <andExpr> { '|' <andExpr> }*
  21.  *
  22.  * <andExpr>        ::= <expr> { <expr> }*
  23.  *
  24.  * <expr>           ::= {'~'} '[' <atomList> ']' <repeatSymbol>
  25.  *                      | '(' <regExpr> ')' <repeatSymbol>
  26.  *                      | '{' <regExpr> '}' <repeatSymbol>
  27.  *                      | <atom> <repeatSymbol>
  28.  *
  29.  * <repeatSymbol>   ::= { '*' | '+' }
  30.  *
  31.  * <atomList>       ::= <atom> { <atom> }*
  32.  *                      | { <atomList> } <atom> '-' <atom> { <atomList> }
  33.  *
  34.  * <atom>           ::= Token[Atom]
  35.  *
  36.  * Notes:
  37.  *        ~    means complement the set in [..]. i.e. all characters not listed
  38.  *        *    means match 0 or more times (can be on expression or atom)
  39.  *        +    means match 1 or more times (can be on expression or atom)
  40.  *        {}    optional
  41.  *        ()    grouping
  42.  *        []    set of atoms
  43.  *        x-y    all characters from x to y (found only in [..])
  44.  *        \xx the character with value xx
  45.  *
  46.  * Examples:
  47.  *        [a-z]+
  48.  *            match 1 or more lower-case letters (e.g. variable)
  49.  *
  50.  *        0x[0-9A-Fa-f]+
  51.  *            match a hex number with 0x on front (e.g. 0xA1FF)
  52.  *
  53.  *        [0-9]+.[0-9]+{e[0-9]+}
  54.  *            match a floating point number (e.g. 3.14e21)
  55.  *
  56.  * Code example:
  57.  *        if ( rexpr("[a-zA-Z][a-zA-Z0-9]+", str) ) then str is keyword
  58.  *
  59.  * Terence Parr
  60.  * Purdue University
  61.  * April 1991
  62.  */
  63.  
  64. #include <stdio.h>
  65. #include <ctype.h>
  66.  
  67. #define Atom    256        /* token Atom (an impossible char value) */
  68. #define Epsilon    257        /* epsilon arc (an impossible char value) */
  69.  
  70. typedef struct _a {
  71.                     int label;
  72.                     struct _a *next;
  73.                     struct _n *target;
  74.                     struct _a *track;    /* track mem allocation */
  75.                 } Arc, *ArcPtr;
  76.  
  77. typedef struct _n {
  78.                     ArcPtr arcs, arctail;
  79.                     struct _n *track;
  80.                 } Node, *NodePtr;
  81.  
  82. typedef struct    {
  83.                     NodePtr left,
  84.                              right;
  85.                 } Graph, *GraphPtr;
  86.  
  87. static char *_c;
  88. static int token, tokchar;
  89. static NodePtr accept;
  90. static NodePtr freelist = NULL;
  91.  
  92. Graph    BuildNFA_Aoptional(),
  93.         BuildNFA_Aplus(),
  94.         BuildNFA_Astar(),
  95.         BuildNFA_set(),
  96.         BuildNFA_AorB(),
  97.         BuildNFA_AB(),
  98.         BuildNFA_atom();
  99. char    *calloc();
  100.  
  101. /*
  102.  * return 1 if s in language described by expr
  103.  *        0 if s is not
  104.  *       -1 if expr is an invalid regular expression
  105.  */
  106. rexpr(expr, s)
  107. char *expr, *s;
  108. {
  109.     NodePtr p,q;
  110.     Graph nfa;
  111.     int result;
  112.  
  113.     fprintf(stderr, "rexpr(%s,%s);\n", expr,s);
  114.     _c = expr;
  115.     next();
  116.     if ( !regExpr(&nfa) ) return -1;
  117.     accept = nfa.right;
  118.     result = match(nfa.left, s);
  119.     /* free all your memory */
  120.     p = q = freelist;
  121.     while ( p!=NULL ) { q = p->track; free(p); p = q; }
  122.     return result;
  123. }
  124.  
  125. /*
  126.  * do a depth-first-search on the NFA looking for a path from start to
  127.  * accept state labelled with the characters of 's'.
  128.  */
  129. match(automaton, s)
  130. NodePtr automaton;
  131. char *s;
  132. {
  133.     ArcPtr p;
  134.     
  135.     if ( automaton == accept && *s == '\0' ) return 1;    /* match */
  136.  
  137.     for (p=automaton->arcs; p!=NULL; p=p->next)            /* try all arcs */
  138.     {
  139.         if ( p->label == Epsilon )
  140.         {
  141.             if ( match(p->target, s) ) return 1;
  142.         }
  143.         else if ( p->label == *s )
  144.                 if ( match(p->target, s+1) ) return 1;
  145.     }
  146.     return 0;
  147. }
  148.  
  149. /*
  150.  * <regExpr>        ::= <andExpr> { '|' <andExpr> }*
  151.  */
  152. static
  153. regExpr(g)
  154. GraphPtr g;
  155. {
  156.     Graph g1, g2;
  157.     
  158.     if ( !andExpr(&g1) )
  159.     {
  160.         return 0;
  161.     }
  162.     
  163.     while ( token == '|' )
  164.     {
  165.         next();
  166.         if ( !andExpr(&g2) )
  167.         {
  168.             return 1;
  169.         }
  170.         g1 = BuildNFA_AorB(g1, g2);
  171.     }
  172.     
  173.     *g = g1;
  174.     return 1;
  175. }
  176.  
  177. /*
  178.  * <andExpr>        ::= <expr> { <expr> }*
  179.  */
  180. static
  181. andExpr(g)
  182. GraphPtr g;
  183. {
  184.     Graph g1, g2;
  185.     
  186.     if ( !expr(&g1) )
  187.     {
  188.         return 0;
  189.     }
  190.     
  191.     while ( expr(&g2) )
  192.     {
  193.         g1 = BuildNFA_AB(g1, g2);
  194.     }
  195.     
  196.     *g = g1;
  197.     return 1;
  198. }
  199.  
  200. /*
  201.  * <expr>           ::=    {'~'} '[' <atomList> ']' <repeatSymbol>
  202.  *                      | '(' <regExpr> ')' <repeatSymbol>
  203.  *                      | '{' <regExpr> '}' <repeatSymbol>
  204.  *                      | <atom> <repeatSymbol>
  205.  */
  206. static
  207. expr(g)
  208. GraphPtr g;
  209. {
  210.     int complement = 0;
  211.     char s[257];    /* alloc space for string of char in [] */
  212.     
  213.     if ( token == '~' || token == '[' )
  214.     {
  215.         if ( token == '~' ) {complement = 1; next();}
  216.         if ( token != '[' ) return 0;
  217.         next();
  218.         atomList( s, complement );
  219.         *g = BuildNFA_set( s );
  220.         if ( token != ']' ) return 0;
  221.         next();
  222.         repeatSymbol( g );
  223.         return 1;
  224.     }
  225.     if ( token == '(' )
  226.     {
  227.         next();
  228.         regExpr( g );
  229.         if ( token != ')' ) return 0;
  230.         next();
  231.         repeatSymbol( g );
  232.         return 1;
  233.     }
  234.     if ( token == '{' )
  235.     {
  236.         next();
  237.         regExpr( g );
  238.         if ( token != '}' ) return 0;
  239.         next();
  240.         /* S p e c i a l  C a s e   O p t i o n a l  {  } */
  241.         if ( token != '*' && token != '+' )
  242.         {
  243.             *g = BuildNFA_Aoptional( *g );
  244.         }
  245.         repeatSymbol( g );
  246.         return 1;
  247.     }
  248.     if ( token == Atom )
  249.     {
  250.         *g = BuildNFA_atom( tokchar );
  251.         next();
  252.         repeatSymbol( g );
  253.         return 1;
  254.     }
  255.     
  256.     return 0;
  257. }
  258.  
  259. /*
  260.  * <repeatSymbol>   ::= { '*' | '+' }
  261.  */
  262. static
  263. repeatSymbol(g)
  264. GraphPtr g;
  265. {
  266.     switch ( token )
  267.     {
  268.         case '*' : *g = BuildNFA_Astar( *g ); next(); break;
  269.         case '+' : *g = BuildNFA_Aplus( *g ); next(); break;
  270.     }
  271. }
  272.  
  273. /*
  274.  * <atomList>       ::= <atom> { <atom> }*
  275.  *                      { <atomList> } <atom> '-' <atom> { <atomList> }
  276.  *
  277.  * a-b is same as ab
  278.  * q-a is same as q
  279.  */
  280. static
  281. atomList(p, complement)
  282. char *p;
  283. int complement;
  284. {
  285.     static unsigned char set[256];        /* no duplicates */
  286.     int first, last, i;
  287.     char *s = p;
  288.     
  289.     if ( token != Atom ) return 0;
  290.     
  291.     while ( token == Atom )
  292.     {
  293.         if ( !set[tokchar] ) *s++ = tokchar;
  294.         set[tokchar] = 1;                /* Add atom to set */
  295.         next();
  296.         if ( token == '-' )             /* have we found '-' */
  297.         {
  298.             first = *(s-1);             /* Get last char */
  299.             next();
  300.             if ( token != Atom ) return 0;
  301.             else
  302.             {
  303.                 last = tokchar;
  304.             }
  305.             for (i = first+1; i <= last; i++)
  306.             {
  307.                 if ( !set[tokchar] ) *s++ = i;
  308.                 set[i] = 1;                /* Add atom to set */
  309.             }
  310.             next();
  311.         }
  312.     }
  313.     *s = '\0';
  314.     if ( complement )
  315.     {
  316.         for (i=0; i<256; i++) set[i] = !set[i];
  317.         for (i=1,s=p; i<256; i++) if ( set[i] ) *s++ = i;
  318.         *s = '\0';
  319.     }
  320.     return 1;
  321. }
  322.  
  323. /* a somewhat stupid lexical analyzer */
  324. static
  325. next()
  326. {
  327.     while ( *_c==' ' || *_c=='\t' || *_c=='\n' ) _c++;
  328.     if ( *_c=='\\' )
  329.     {
  330.         _c++;
  331.         if ( isdigit(*_c) )
  332.         {
  333.             int n=0;
  334.             while ( isdigit(*_c) )
  335.             {
  336.                 n = n*10 + (*_c++ - '0');
  337.             }
  338.             if ( n>255 ) n=255;
  339.             tokchar = n;
  340.         }
  341.         else
  342.         {
  343.             switch (*_c)
  344.             {
  345.                 case 'n' : tokchar = '\n'; break;
  346.                 case 't' : tokchar = '\t'; break;
  347.                 case 'r' : tokchar = '\r'; break;
  348.                 default  : tokchar = *_c;
  349.             }
  350.             _c++;
  351.         }
  352.         token = Atom;
  353.     }
  354.     else if ( isgraph(*_c) && *_c!='[' && *_c!='(' && *_c!='{' &&
  355.               *_c!='-' && *_c!='}' && *_c!=')' && *_c!=']' &&
  356.               *_c!='+' && *_c!='*' && *_c!='~' && *_c!='|' )
  357.     {
  358.         token = Atom;
  359.         tokchar = *_c++;
  360.     }
  361.     else
  362.     {
  363.         token = tokchar = *_c++;
  364.     }
  365. }
  366.  
  367. /* N F A  B u i l d i n g  R o u t i n e s */
  368.  
  369. static
  370. ArcPtr
  371. newGraphArc()
  372. {
  373.     ArcPtr p;
  374.     p = (ArcPtr) calloc(1, sizeof(Arc));
  375.     if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
  376.     if ( freelist != NULL ) p->track = (ArcPtr) freelist;
  377.     freelist = (NodePtr) p;
  378.     return p;
  379. }
  380.  
  381. static
  382. NodePtr
  383. newNode()
  384. {
  385.     NodePtr p;
  386.     p = (NodePtr) calloc(1, sizeof(Node));
  387.     if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
  388.     if ( freelist != NULL ) p->track = freelist;
  389.     freelist = p;
  390.     return p;
  391. }
  392.  
  393. static
  394. ArcBetweenGraphNodes(i, j, label)
  395. NodePtr i, j;
  396. int label;
  397. {
  398.     ArcPtr a;
  399.     
  400.     a = newGraphArc();
  401.     if ( i->arcs == NULL ) i->arctail = i->arcs = a;
  402.     else {(i->arctail)->next = a; i->arctail = a;}
  403.     a->label = label;
  404.     a->target = j;
  405. }
  406.  
  407. static Graph
  408. BuildNFA_atom(label)
  409. int label;
  410. {
  411.     Graph g;
  412.     
  413.     g.left = newNode();
  414.     g.right = newNode();
  415.     ArcBetweenGraphNodes(g.left, g.right, label);
  416.     return( g );
  417. }
  418.  
  419. static Graph
  420. BuildNFA_AB(A, B)
  421. Graph A, B;
  422. {
  423.     Graph g;
  424.     
  425.     ArcBetweenGraphNodes(A.right, B.left, Epsilon);
  426.     g.left = A.left;
  427.     g.right = B.right;
  428.     return( g );
  429. }
  430.  
  431. static Graph
  432. BuildNFA_AorB(A, B)
  433. Graph A, B;
  434. {
  435.     Graph g;
  436.     
  437.     g.left = newNode();
  438.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  439.     ArcBetweenGraphNodes(g.left, B.left, Epsilon);
  440.     g.right = newNode();
  441.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  442.     ArcBetweenGraphNodes(B.right, g.right, Epsilon);
  443.     return( g );
  444. }
  445.  
  446. static Graph
  447. BuildNFA_set( s )
  448. char *s;
  449. {
  450.     Graph g;
  451.     
  452.     if ( s == NULL ) return g;
  453.     
  454.     g.left = newNode();
  455.     g.right = newNode();
  456.     while ( *s != '\0' )
  457.     {
  458.         ArcBetweenGraphNodes(g.left, g.right, *s++);
  459.     }
  460.     return g;
  461. }
  462.  
  463. static Graph
  464. BuildNFA_Astar( A )
  465. Graph A;
  466. {
  467.     Graph g;
  468.  
  469.     g.left = newNode();
  470.     g.right = newNode();
  471.     
  472.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  473.     ArcBetweenGraphNodes(g.left, g.right, Epsilon);
  474.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  475.     ArcBetweenGraphNodes(A.right, A.left, Epsilon);
  476.     
  477.     return( g );
  478. }
  479.  
  480. static Graph
  481. BuildNFA_Aplus( A )
  482. Graph A;
  483. {
  484.     ArcBetweenGraphNodes(A.right, A.left, Epsilon);
  485.     
  486.     return( A );
  487. }
  488.  
  489. static Graph
  490. BuildNFA_Aoptional( A )
  491. Graph A;
  492. {
  493.     Graph g;
  494.     
  495.     g.left = newNode();
  496.     g.right = newNode();
  497.     
  498.     ArcBetweenGraphNodes(g.left, A.left, Epsilon);
  499.     ArcBetweenGraphNodes(g.left, g.right, Epsilon);
  500.     ArcBetweenGraphNodes(A.right, g.right, Epsilon);
  501.     
  502.     return( g );
  503. }
  504.